package com.demo.java.OD201_250.OD231;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【寻找密码】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145932170
 */
public class OdMain {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            // 读取输入的密码字符串
            String line = s.nextLine();
            String result = solveMethod(line);
            System.out.println(result); // 输出结果
        }
    }

    private static String solveMethod(String line) {
        // 分割输入的密码集合
        String[] split = line.split(" ");
        // 按照字典序排序
        Arrays.sort(split);
        // 初始化Trie树
        Trie trie = new Trie();

        // 向Trie中插入所有密码
        for (String word : split) {
            trie.insert(word);
        }

        // 从最长的密码开始检查
        for (int i = split.length - 1; i >= 0; --i) {
            String pw = split[i];
            boolean flag = true;
            // 检查密码的所有前缀
            for (int j = pw.length() - 1; j > 0; j--) {
                String tmp = pw.substring(0, j);
                // 如果前缀不存在，跳过该密码
                if (!trie.searchPrefix(tmp)) {
                    flag = false;
                    break;
                }
            }
            // 如果所有前缀都存在，返回当前密码
            if (flag) {
                return pw;
            }
        }
        return ""; // 如果没有符合的密码，返回空字符串
    }
}